/* Copyright Mauro Santoss
 * 
 */
package neo.aoi.octree;

import java.util.ArrayList;

import neo.aoi.Triangle;
import neo.aoi.Voxel;
import artofillusion.math.BoundingBox;
import artofillusion.math.Vec3;

//import artofillusion.raytracer.RTObject;
//import artofillusion.raytracer.Ray;
//import artofillusion.raytracer.Raytracer;

/**
 * This class represents a node in an octree, used for sorting the objects by
 * location in the scene. OctreeNodes can be terminal nodes, in which case they
 * contain a list of objects, or branch nodes, in which case they contain a list
 * of other nodes.
 * <p>
 * This class is more sophisticated than most octrees. When it subdivides a
 * node, it does not simply cut it in half along each axis. Instead, it tries to
 * determine the optimal place to subdivide along each axis, based on the
 * bounding boxes of the objects within the node.
 */

public class OctreeNode extends BoundingBox {
	OctreeNode parent, child0, child1, child2, child3, child4, child5, child6,
			child7;
	Triangle[] triangles;
	double midx, midy, midz;
	double res;
	int depth, index;

	private static final Triangle[] EMPTY_OBJECT_LIST = new Triangle[0];

	public OctreeNode(BoundingBox b) {
		super(b);
	}

	/**
	 * The constructor takes a bounding box, an array of objects, an array of
	 * bounding boxes of the objects, and a reference to its parent node.
	 * treeDepth is the depth of this node in the octree, and maxDepth is the
	 * maximum allowed depth.
	 * @param maxRes
	 *            TODO
	 */

	public OctreeNode(double minx, double maxx, double miny, double maxy,
			double minz, double maxz, Triangle[] tri, OctreeNode parentNode,
			double maxRes) {
		super(minx, maxx, miny, maxy, minz, maxz);
		boolean inside[] = new boolean[tri.length];
		int count, i;

		parent = parentNode;

		if (parentNode == null) {
			this.depth = 0;
			this.index = 1;
		} else {	
			this.index = this.index + 1;
			depth = parent.depth + 1;
		}
		
		res = Math.abs(maxx - minx);
		double halfRes = res / 2;

		// Find which objects are actually inside this node.
		Voxel voxel = new Voxel(new Vec3(minx + halfRes, miny + halfRes, minz
				+ halfRes), res);
		count = 0;
		for (i = 0; i < tri.length; i++) {
			if (voxel.intersects(tri[i])) {
				inside[i] = true;
				count++;
			}
		}

		if (count == 0) {
			triangles = EMPTY_OBJECT_LIST;
			return;
		}

		// Build lists of the objects which are inside this node, and their
		// bounding boxes.

		triangles = new Triangle[count];
		count = 0;
		for (i = 0; i < tri.length; i++) {
			if (inside[i]) {
				triangles[count] = tri[i];
				count++;
			}
		}
		System.out.println("octreenode:octree:" + this.toString() + ",depth:"
				+ depth + ",res:" + res + ",index" + this.index);
		subdivide(maxRes);
	}

	public OctreeNode(double minx, double midx2, double miny, double midy2,
			double minz, double midz2, OctreeNode parentNode, int index2) {
		// TODO Auto-generated constructor stub
		super(minx,  midx2, miny, midy2, minz, midz2);

		parent = parentNode;

		this.index = index2;

		depth = parent.depth + 1;
		
		res = Math.abs(maxx - minx);
		double halfRes = res / 2;

	}

	/**
	 * Determine whether this node should be subdivided. If so, create the child
	 * nodes. Otherwise, mark it as a terminal node.
	 * 
	 * @param maxDepth
	 *            TODO
	 * @param maxRes
	 *            TODO
	 */

	private void subdivide(double maxRes) {

		if (triangles.length > 1) {

			if (res > maxRes) {
				findMidpoints();
				child0 = new OctreeNode(minx, midx, miny, midy, minz, midz,
						triangles, this, maxRes);
				child1 = new OctreeNode(minx, midx, miny, midy, midz, maxz,
						triangles, this, maxRes);
				child2 = new OctreeNode(minx, midx, midy, maxy, minz, midz,
						triangles, this, maxRes);
				child3 = new OctreeNode(minx, midx, midy, maxy, midz, maxz,
						triangles, this, maxRes);
				child4 = new OctreeNode(midx, maxx, miny, midy, minz, midz,
						triangles, this, maxRes);
				child5 = new OctreeNode(midx, maxx, miny, midy, midz, maxz,
						triangles, this, maxRes);
				child6 = new OctreeNode(midx, maxx, midy, maxy, minz, midz,
						triangles, this, maxRes);
				child7 = new OctreeNode(midx, maxx, midy, maxy, midz, maxz,
						triangles, this, maxRes);
				triangles = null;
			} else {
				return;
			}
		} else {
			return;
		}
	}

	/**
	 * 
	 */
	public void divide(int index) {

		findMidpoints();
		child0 = new OctreeNode(minx, midx, miny, midy, minz, midz,this,index+1);
		child1 = new OctreeNode(minx, midx, miny, midy, midz, maxz,
				this,index+2);
		child2 = new OctreeNode(minx, midx, midy, maxy, minz, midz,
				this,index+3);
		child3 = new OctreeNode(minx, midx, midy, maxy, midz, maxz,
				this,index+4);
		child4 = new OctreeNode(midx, maxx, miny, midy, minz, midz,
				this,index+5);
		child5 = new OctreeNode(midx, maxx, miny, midy, midz, maxz,
				this,index+6);
		child6 = new OctreeNode(midx, maxx, midy, maxy, minz, midz,
				this,index+7);
		child7 = new OctreeNode(midx, maxx, midy, maxy, midz, maxz,
				this,index+8);


	}

	/** Build a list of all child nodes. */

	public OctreeNode[] findChildNodes() {
		ArrayList nodes = new ArrayList();
		if (child0 != null)
			nodes.add(child0);
		if (child1 != null)
			nodes.add(child1);
		if (child2 != null)
			nodes.add(child2);
		if (child3 != null)
			nodes.add(child3);
		if (child4 != null)
			nodes.add(child4);
		if (child5 != null)
			nodes.add(child5);
		if (child6 != null)
			nodes.add(child6);
		if (child7 != null)
			nodes.add(child7);
		return (OctreeNode[]) nodes.toArray(new OctreeNode[nodes.size()]);
	}

	/** Get the list of objects in this node. */

	public Triangle[] getTriangles() {
		return triangles;
	}

	/**
	 * This method should be called on the root node of the octree. Given a
	 * point, return the terminal node which contains it. If the point is not
	 * inside this node, return null.
	 */

	public OctreeNode findNode(Vec3 pos) {
		OctreeNode current;

		if (!contains(pos))
			return null;
		current = this;
		while (current.triangles == null) {
			if (pos.x > current.midx) {
				if (pos.y > current.midy) {
					if (pos.z > current.midz)
						current = current.child7;
					else
						current = current.child6;
				} else {
					if (pos.z > current.midz)
						current = current.child5;
					else
						current = current.child4;
				}
			} else {
				if (pos.y > current.midy) {
					if (pos.z > current.midz)
						current = current.child3;
					else
						current = current.child2;
				} else {
					if (pos.z > current.midz)
						current = current.child1;
					else
						current = current.child0;
				}
			}
		}
		return current;
	}

	/**
	 * Given a ray which passes through this node, find the next node it passes
	 * through. If this is the last node it passes through, return null.
	 */

	// public OctreeNode findNextNode(Ray r) {
	// double maxt = Double.MAX_VALUE;
	// double dx = 0.0, dy = 0.0, dz = 0.0;
	// Vec3 orig = r.getOrigin(), dir = r.getDirection();
	//
	// if (parent == null)
	// return null;
	//
	// // Find the last point on the ray which is inside this node.
	//
	// if (dir.x > Raytracer.TOL) {
	// dx = Raytracer.TOL;
	// double t = (maxx - orig.x) / dir.x;
	// if (t < maxt)
	// maxt = t;
	// } else if (dir.x < -Raytracer.TOL) {
	// dx = -Raytracer.TOL;
	// double t = (minx - orig.x) / dir.x;
	// if (t < maxt)
	// maxt = t;
	// }
	// if (dir.y > Raytracer.TOL) {
	// dy = Raytracer.TOL;
	// double t = (maxy - orig.y) / dir.y;
	// if (t < maxt)
	// maxt = t;
	// } else if (dir.y < -Raytracer.TOL) {
	// dy = -Raytracer.TOL;
	// double t = (miny - orig.y) / dir.y;
	// if (t < maxt)
	// maxt = t;
	// }
	// if (dir.z > Raytracer.TOL) {
	// dz = Raytracer.TOL;
	// double t = (maxz - orig.z) / dir.z;
	// if (t < maxt)
	// maxt = t;
	// } else if (dir.z < -Raytracer.TOL) {
	// dz = -Raytracer.TOL;
	// double t = (minz - orig.z) / dir.z;
	// if (t < maxt)
	// maxt = t;
	// }
	//
	// // Push it just outside this node, then move up the tree to find a node
	// // that
	// // contains it.
	//
	// Vec3 nextPos = r.tempVec1;
	// nextPos.set(orig.x + dir.x * maxt + dx, orig.y + dir.y * maxt + dy,
	// orig.z + dir.z * maxt + dz);
	// OctreeNode current = parent;
	// while (!current.contains(nextPos)) {
	// current = current.parent;
	// if (current == null)
	// return null;
	// }
	//
	// // Now move back down the tree until we reach a terminal node.
	//
	// while (current.triangles == null) {
	// if (nextPos.x > current.midx) {
	// if (nextPos.y > current.midy) {
	// if (nextPos.z > current.midz)
	// current = current.child7;
	// else
	// current = current.child6;
	// } else {
	// if (nextPos.z > current.midz)
	// current = current.child5;
	// else
	// current = current.child4;
	// }
	// } else {
	// if (nextPos.y > current.midy) {
	// if (nextPos.z > current.midz)
	// current = current.child3;
	// else
	// current = current.child2;
	// } else {
	// if (nextPos.z > current.midz)
	// current = current.child1;
	// else
	// current = current.child0;
	// }
	// }
	// }
	// return current;
	// }

	/**
	 * This method should be called on the root node of the octree. Given a ray
	 * whose origin is outside the node, find the point where it enters the
	 * node, and return the terminal node which contains that point. If the ray
	 * never intersects this node, return null.
	 */

	// public OctreeNode findFirstNode(Ray r) {
	// double t1, t2, mint = -Double.MAX_VALUE, maxt = Double.MAX_VALUE;
	// Vec3 orig = r.getOrigin(), dir = r.getDirection();
	//
	// // Find the point where the ray enters this node (if it does at all).
	//
	// if (dir.x == 0.0) {
	// if (orig.x < minx || orig.x > maxx)
	// return null;
	// } else {
	// t1 = (minx - orig.x) / dir.x;
	// t2 = (maxx - orig.x) / dir.x;
	// if (t1 < t2) {
	// if (t1 > mint)
	// mint = t1;
	// if (t2 < maxt)
	// maxt = t2;
	// } else {
	// if (t2 > mint)
	// mint = t2;
	// if (t1 < maxt)
	// maxt = t1;
	// }
	// if (mint > maxt || maxt < 0.0)
	// return null;
	// }
	// if (dir.y == 0.0) {
	// if (orig.y < miny || orig.y > maxy)
	// return null;
	// } else {
	// t1 = (miny - orig.y) / dir.y;
	// t2 = (maxy - orig.y) / dir.y;
	// if (t1 < t2) {
	// if (t1 > mint)
	// mint = t1;
	// if (t2 < maxt)
	// maxt = t2;
	// } else {
	// if (t2 > mint)
	// mint = t2;
	// if (t1 < maxt)
	// maxt = t1;
	// }
	// if (mint > maxt || maxt < 0.0)
	// return null;
	// }
	// if (dir.z == 0.0) {
	// if (orig.z < minz || orig.z > maxz)
	// return null;
	// } else {
	// t1 = (minz - orig.z) / dir.z;
	// t2 = (maxz - orig.z) / dir.z;
	// if (t1 < t2) {
	// if (t1 > mint)
	// mint = t1;
	// if (t2 < maxt)
	// maxt = t2;
	// } else {
	// if (t2 > mint)
	// mint = t2;
	// if (t1 < maxt)
	// maxt = t1;
	// }
	// if (mint > maxt || maxt < 0.0)
	// return null;
	// }
	//
	// // Push it just inside this node.
	//
	// mint += Raytracer.TOL;
	// Vec3 nextPos = r.tempVec1;
	// nextPos.set(orig.x + dir.x * mint, orig.y + dir.y * mint, orig.z
	// + dir.z * mint);
	//
	// // Return the terminal node which contains the point.
	//
	// return findNode(nextPos);
	// }

	/**
	 * Analyze the distribution of objects inside this node, and determine the
	 * best place at which to subdivide it along each axis.
	 */

	public void findMidpoints() {

		// If the box is much shorter along one axis than the other two, we
		// don't want to subdivide
		// along that axis, since it would slow down many more rays than it
		// would speed up.

		// Vec3 size = getSize();

		midx = minx + res / 2;
		midy = miny + res / 2;
		midz = minz + res / 2;
	}

}